KRI Wilhelmus Zakarias Yohannes (Gurkha) dibina oleh John I. Thornycroft & Company, dari Woolston, Hampshire,[2] pada kos £4,865,000[3] Ia dilancarkan pada 11 Julai 1960 dan ditauliah pada 13 Februari 1963.[2]

Pada tahun 1975, Gurkha ditempatkan di Indies Barat bagi pelbagai tugasan. Pada tahun 1976, Gurkha menyokong usaha Tentera Laut British terhadap Iceland semasa Perang Kod Ketiga. Ia mengalami sedikit kerosakan pada bulan May apabila kapal peronda Óðinn cuba memaksa kapal terhadap bot pukat tunda British Ross Ramilles, ketika masa Óðinn berlanggar dengan Gurkha.[4]

Gurkha hadir pada Penilaian Armada 1977 Spithead, diadakan bagi penghormatan bagi Jubli Perak Ratu Elizabeth II Silver Jubilee.

Gurkha dijadikan simpanan pada tahun 1980, diletakkan di bawah skuarden Berjaga-jaga. Sungguhpun ia diletakkan dalam daftar pelupusan,[5] Gurkha dikeluarkan dari simpanan semasa Perang Falklands dan disediakan bagi perkhidmatan aktif.[6] Gurkha kekal di perairan negara, memenuhi tigasan semasa ketiadaan kapal yang beroperasi di Atlantik Selatan.